//给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。 
//
// 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [3,6,9,1]
//输出: 3
//解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 
//
// 示例 2: 
//
// 
//输入: nums = [10]
//输出: 0
//解释: 数组元素个数小于 2，因此返回 0。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 10⁵ 
// 0 <= nums[i] <= 10⁹ 
// 
//
// Related Topics 数组 桶排序 基数排序 排序 👍 652 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maximumGap(int[] nums) {
        //1.
//        if(nums.length<2) {
//            return 0;
//        }
//        Arrays.sort(nums);
//        int maxDiff = 0;
//        int pre = nums[0];
//        for (int num : nums) {
//            maxDiff = Math.max(maxDiff, num - pre);
//            pre = num;
//        }
//        return maxDiff;
        //2.基数排序
        if(nums.length<2)
            return 0;

        //2.1基数排序开始,先取最大值，再分配十个桶
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int bucketNum = 10;
        ArrayList<Integer> [] buckets = new ArrayList[bucketNum];
        for(int i = 0; i< bucketNum; i++){
            buckets[i] = new ArrayList();//每个桶用数组存数据
        }
        int m = 1; //第一轮:num / 1 % 10,第二轮: num/10 %10,第三轮: num/100 %10
        while(m <= max){
            for (int num : nums) {
                buckets[num/m%10].add(num);
            }
            int k = 0;//N轮排序后nums的起始索引
            for (ArrayList<Integer> bucket : buckets) {
                for(Integer integer:bucket){
                    nums[k++] = integer;
                }
                bucket.clear();//清空桶，准备下次用
            }
            m=m*10;
        }




        int maxDiff = 0;
        int pre = nums[0];
        for (int num : nums) {
            maxDiff = Math.max(maxDiff, num - pre);
            pre = num;
        }
        return maxDiff;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
